package com.wyd.common.util;

import lombok.Getter;
import lombok.Setter;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 转换树结构工具
 */
public class TreeUtil {
    private TreeUtil() {}

    @Setter
    @Getter
    public static class Tree<T extends Tree<T>> {
        private String id;
        private String pid;
        private List<T> children;

        public Tree() {
        }

        public Tree(String id, String pid) {
            this.id = id;
            this.pid = pid;
        }
    }

    /**
     * 转换为map
     * 以空间换时间
     * 速度最快
     */
    public static <T extends Tree<T>> List<T> build(List<T> list, String topPid) {
        // LinkedHashMap 保持原有顺序
        final Map<String, List<T>> map = list.stream().collect(Collectors.groupingBy(T::getPid, LinkedHashMap::new, Collectors.toList()));

        return build(map, topPid);
    }

    private static <T extends Tree<T>> List<T> build(Map<String, List<T>> map, String topPid) {
        final List<T> topList = map.get(topPid);

        // 删除，避免出现循环树
        map.remove(topPid);

        if (topList == null) {
            return Collections.emptyList();
        }

        topList.parallelStream().forEach(t -> t.setChildren(build(map, t.getId())));

        return topList;
    }

    /**
     * 使用的parallelStream并行处理，输出是无序的
     * 速度较快
     * 如果数据中有循环父子结构会报错
     */
    public static <T extends Tree<T>> List<T> build3(List<T> list, String topPid) {
        final ArrayList<T> topList = new ArrayList<>();
        // 并行提速
        list.parallelStream().forEach(t -> {
            if (t.getPid().equals(topPid)) {

                t.setChildren(build3(list, t.getId()));

                topList.add(t);
            }
        });

        return topList;
    }

    /**
     * 使用集合倒叙循环，边查找边删除
     * 错误代码
     * (这个是曾经写的错误代码！！)
     */
//    public static <T extends Tree<T>> List<T> build2(List<T> list, String topPid) {
//        final ArrayList<T> topList = new ArrayList<>();
//
//        for (int i = list.size() - 1; i >= 0; i--) {
//            final T t = list.get(i);
//
//            if (t.getPid().equals(topPid)) {
//                list.remove(i);
//
//                t.setChildren(build2(list, t.getId()));
//
//                topList.add(t);
//            }
//        }
//
//        return topList;
//    }

    /**
     * 普通全部循环的方式进行构建树结构
     * 速度较慢
     * 如果数据中有循环父子结构会报错
     */
    public static <T extends Tree<T>> List<T> build2(List<T> list, String topPid) {
        final ArrayList<T> topList = new ArrayList<>();

        for (T t : list) {
            if (t.getPid().equals(topPid)) {
                t.setChildren(build2(list, t.getId()));

                topList.add(t);
            }
        }

        return topList;
    }
}
